package algo;

import edu.uci.ics.jung.graph.Graph;
import facility.Facility;
import graph.CustNode;
import graph.NetworkPoint;
import graph.GraphEdge;
import graph.GraphFactory;
import graph.GraphNode;
import io.DataReader;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import rtree.RTree;
import rtree.RTreeUtil;
import spatialindex.Circle;
import spatialindex.ISpatialIndex;
import spatialindex.Point;
import spatialindex.Region;
import storagemanager.IBuffer;
import storagemanager.IStorageManager;
import storagemanager.MemoryStorageManager;
import storagemanager.PropertySet;
import storagemanager.RandomEvictionsBuffer;
import util.MathUtil;

public class MaxFirstNet {

	/**
	 * Now I have osmReader and textReader.
	 * 
	 * TODO:
	 * 1. read cnodes and facilities [done]
	 * 2. foreach customer c compute c's k nearest facilities [done]
	 * use mapping format: cid=> fid_1 dist_1 fid_2 dist_2 ... [done]
	 * 3. find out the ELocation for a cNode, and cnode.setEloc() [done]
	 * 5. make sure the edges have the facilies and cnodes
	 * 
	 * @param args
	 * @author xiaohui
	 */

	private static String vertexFile = "D:/research/maxfirst/expt/vertices.txt";
	private static String edgeFile = "D:/research/maxfirst/expt/edges.txt";
	private static String facilityFile = "D:/research/maxfirst/expt/facilities.txt";
	private static String cnodesFile = "D:/research/maxfirst/expt/cnodes.txt";
	private static int k = 5;
	private static int numTrials = 5;

	private static String edgeTreeFile = "D:/research/maxfirst/expt/RTreetestIdx";
	private static String fTreeFile = "D:/research/maxfirst/expt/fRTreeIdx";
	private static String distFile = "D:/research/maxfirst/expt/distMat";
	private static int numVerticesToRead = 2500;
	private static int numEdgesToRead = 2500;
	private static int numCnodesToRead = 2500;
	private static int numFacilitiesToRead = 1600;

	static Map<Integer, SegScore> edgeIdToSegmentScoreMap = new HashMap<Integer, SegScore>(
			Share.initHashMapSize);

	public static void main(String[] args) throws IOException {
		System.out.println("loading vertices...");
		HashMap<Integer, GraphNode> verticesMap = DataReader.loadVertices(
				vertexFile, numVerticesToRead);
		System.out.println("loading edges...");
		HashMap<Integer, GraphEdge> edgesMap = DataReader.loadEdges(
				verticesMap, edgeFile, 1, numEdgesToRead);

		Graph<GraphNode, GraphEdge> graph = GraphFactory
				.createDirectedSparseGraph(verticesMap, edgesMap);

		// load facilities and customer sites
		Map<Integer, Facility> facilitiesMap = DataReader.loadFacilities(
				facilityFile, edgesMap, numFacilitiesToRead);

		Map<Integer, CustNode> cnodesMap = DataReader.loadCNodes(cnodesFile,
				numCnodesToRead);

		// index edges
		System.out.println("indexing edges with RTree");
		ISpatialIndex eRTree = RTreeLoadEdges(32, edgesMap);

		// assign elocation to each cnode
		for (CustNode cnode : cnodesMap.values()) {
			NetworkPoint cel = MapMatcher.mapMatch(cnode, numTrials, edgesMap,
					eRTree);
			cnode.setEloc(cel);
		}

		// find the network distance to the top5 nearest facilities
		// step 1. pre-compute pair-wise distance between any two vertices
		// the index are the identifiers of the two nodes
		int size = verticesMap.size();
		double[][] distMatrix = new double[size][size];
		Set<Integer> keys = verticesMap.keySet();
		Collection<GraphNode> vertices = verticesMap.values();
		GraphNode[] vArr = vertices.toArray(new GraphNode[vertices.size()]);
		for (int i = 0; i < vArr.length; i++) {
			for (int j = i + 1; j < vArr.length; j++) {
				distMatrix[vArr[i].getId()][vArr[j].getId()] = MathUtil
						.computeNetworkDistance(graph, vArr[i], vArr[j]);
			}
		}
		// output the distMatrix to file
		outToFile(distMatrix, distFile);

		// step 1.1 index the facilities with a RTree
		ISpatialIndex fRTree = RTreeLoadFacilities(32, facilitiesMap);

		// step 2. find the edge where the customer is located and the edge
		RTreeUtil rTreeUtil = new RTreeUtil();
		for (CustNode cnode : cnodesMap.values()) {
			NetworkPoint cel = cnode.getEloc();

			GraphNode cgn = edgesMap.get(cel.getEdgeId()).getSrcNode();

			double[] point = { cnode.getX(), cnode.getY() };
			// get ids of the facilities with Euclidean distancs
			List<Integer> nnlist = rTreeUtil.RTreeQuery(fRTree, k + "NN",
					point, null);

			// pass the list to get the furthest facility
			// to ensure at least k facilities are inside
			double maxDist = Double.MIN_VALUE;
			int maxDistFid = -1;
			for (int i : nnlist) {
				Facility f = facilitiesMap.get(i);
				NetworkPoint fel = f.getEloc();
				// f.set

//				double dist = computeNetworkDist(cel, fel, edgesMap, distMatrix);
				double dist =0;
				if (maxDist < dist) {
					maxDist = dist;
					maxDistFid = i;
				}
			}

			/**
			 * 1. overlap eRTree with the rectangle that bounds
			 * the circle with radius
			 * being the longest network distance between cnode and
			 * its knn facility => list of eids
			 * 
			 * 2.1 retrieve the facilities on the edges from step 1,
			 * 2.2 sort the facilities according to the distances
			 * 2.3 calculate the true knn distance
			 * 
			 * 3. assign scores to the segments within the knn distance
			 **/

			double[] point1 = { cnode.getX() - maxDist, cnode.getY() - maxDist };
			double[] point2 = { cnode.getX() + maxDist, cnode.getY() + maxDist };
			List<Integer> eids = rTreeUtil.RTreeQuery(eRTree, "intersection",
					point1, point2);

			List<FaDist> fDistList = new ArrayList<FaDist>(2 * k);
			for (Integer eid : eids) {
				GraphEdge ge = edgesMap.get(eid);
				for (int fid : ge.getFids()) {
					Facility tempFaci = facilitiesMap.get(fid);
					NetworkPoint tempFel = tempFaci.getEloc();
//					double tempDist = computeNetworkDist(cel, tempFel,
//							edgesMap, distMatrix);
					double tempDist =0;
					fDistList.add(new FaDist(tempFaci.getId(), tempDist));
				}
			}

			Collections.sort(fDistList);

			double trueDist = fDistList.get(k - 1).dist;
			// complete the circle definition
			for (Integer eid : eids) {
				GraphEdge ge = edgesMap.get(eid);
//				assignScore(cnode, ge, trueDist, graph, edgesMap, distMatrix);
			}

		}

	}

//	/**
//	 * assign score to the edge ge
//	 * 
//	 * @param cnode
//	 * @param c
//	 * @param ge
//	 * @param knnDist
//	 */
//	private static void assignScore(CustNode cnode, GraphEdge ge,
//			double knnDist, Graph graph, Map<Integer, GraphEdge> edgesmap,
//			double[][] distMatrix) {
//		/**
//		 * There are three cases:
//		 * 1. no end of an edge is inside of the circle=> no score assignment
//		 * 2. one end of an edge is inside => (0, ratio, score)
//		 * 3. two ends of an edge are inside => (0, 1, score)
//		 */
//		GraphNode src1 = ge.getSrcNode();
//		GraphNode dest1 = ge.getDestNode();
//		// need to use network distance
//		// get cnode's edge
//		GraphEdge e0 = edgesmap.get(cnode.getEloc().getEdgeId());
//		GraphNode src0 = e0.getSrcNode();
//		GraphNode dest0 = e0.getDestNode();
//
//		// if pass src0, how long is the distance from cnode to src1
//		double sd_src = distMatrix[src0.getId()][src1.getId()]
//				+ cnode.getEloc().getDistFromNode();
//		double sd_dest = distMatrix[src0.getId()][dest1.getId()]
//				+ cnode.getEloc().getDistFromNode();
//
//		// if pass dest0, how long is the distance from cnode to dest1
//		double length = ge.getWeight();
//		double dd_src = distMatrix[dest0.getId()][src1.getId()]
//				+ (length - cnode.getEloc().getDistFromNode());
//		double dd_dest = distMatrix[dest0.getId()][src1.getId()]
//				+ (length - cnode.getEloc().getDistFromNode());
//
//		double smallest = MathUtil.min(sd_src, sd_dest, dd_src, dd_dest);
//
//		if (smallest >= knnDist) {
//			// case 1
//			// do nothing
//			return;
//		}
//
//		// find out the passing node on ge
//		GraphNode tempNode = null;
//		if (smallest == sd_src || smallest == dd_src) {
//			tempNode = src1;
//		} else {
//			tempNode = dest1;
//		}
//
//		if (tempNode.equals(src1)) {
//			if (dd_dest <= knnDist || sd_dest <= knnDist) {
//				// case 3, the whole ge gets score
//				SegScore segscore = new SegScore(0, 1, cnode.getScore());
//				// add to the global mapping
//				edgeIdToSegmentScoreMap.put(ge.getId(), segscore);
//			} else {
//				// case 2, src is in, but dest is not
//				double ratioFromSrc = (knnDist - smallest) / length;
//
//				edgeIdToSegmentScoreMap.put(ge.getId(), new SegScore(0,
//						ratioFromSrc, cnode.getScore()));
//
//			}
//		} else if (tempNode.equals(dest1)) {
//			if (dd_src <= knnDist || sd_src <= knnDist) {
//				// case 3, the whole ge gets score
//				SegScore segscore = new SegScore(0, 1, cnode.getScore());
//				// add to the global mapping
//				edgeIdToSegmentScoreMap.put(ge.getId(), segscore);
//			}
//
//			else {
//				// case 2, dest is in, but src of ge is not
//				double ratio = (knnDist - smallest) / length;
//				edgeIdToSegmentScoreMap.put(ge.getId(), new SegScore(ratio, 1,
//						cnode.getScore()));
//			}
//		}
//
//	}

//	/**
//	 * 
//	 * @param src
//	 * @param dest
//	 * @param edgesMap
//	 * @param distMatrix
//	 * @return the shortest network distance between two elocations
//	 */
//	private static double computeNetworkDist(NetworkPoint srcEloc,
//			NetworkPoint destEloc, Map<Integer, GraphEdge> edgesMap,
//			double[][] distMatrix) {
//		GraphEdge srcEdge = edgesMap.get(srcEloc.getEdgeId());
//		GraphEdge destEdge = edgesMap.get(destEloc.getEdgeId());
//
//		double srcLength = srcEdge.getWeight();
//		double destLength = destEdge.getWeight();
//
//		GraphNode src0 = srcEdge.getSrcNode();
//		GraphNode dest0 = srcEdge.getDestNode();
//
//		GraphNode src1 = destEdge.getSrcNode();
//		GraphNode dest1 = destEdge.getDestNode();
//
//		// if pass src0, how long is the distance from cnode to src1
//		double dist_src_src = distMatrix[src0.getId()][src1.getId()]
//				+ srcEloc.getDistFromNode() + destEloc.getDistFromNode();
//
//		double dist_src_dest = distMatrix[src0.getId()][dest1.getId()]
//				+ srcEloc.getDistFromNode()
//				+ (destLength - destEloc.getDistFromNode());
//
//		// if pass dest0, how long is the distance from cnode to dest1
//		double dist_dest_src = distMatrix[dest0.getId()][src1.getId()]
//				+ (srcLength - srcEloc.getDistFromNode())
//				+ destEloc.getDistFromNode();
//
//		double dist_dest_dest = distMatrix[dest0.getId()][dest1.getId()]
//				+ (srcLength - srcEloc.getDistFromNode()) + destLength
//				- destEloc.getDistFromNode();
//
//		return MathUtil.min(dist_src_src, dist_src_dest, dist_dest_src,
//				dist_dest_dest);
//	}

	
	/**
	 * 
	 * @param distMatrix
	 * @param filename
	 */
	private static void outToFile(double[][] distMatrix, String filename) {
		// TODO Auto-generated method stub

	}

	/**
	 * 
	 * @param treeFile
	 * @param capacity
	 * @param facilitiesMap
	 * @return a facility RTree
	 */
	static ISpatialIndex RTreeLoadFacilities(int capacity,
			Map<Integer, Facility> facilitiesMap) {
		ISpatialIndex fRTree = null;
		try {

			// specify the page size. Since the index may also contain user
			// defined data
			// there is no way to know how big a single node may become. The
			// storage manager
			// will use multiple pages per node if needed. Off course this will
			// slow down performance.

			IStorageManager diskfile = new MemoryStorageManager();
			// IStorageManager diskfile = new DiskStorageManager(ps);

			IBuffer file = new RandomEvictionsBuffer(diskfile, 10, false);
			// applies a main memory random buffer on top of the persistent
			// storage manager
			// (LRU buffer, etc can be created the same way).

			// Create a new, empty, RTree with dimensionality 2, minimum load
			// 70%, using "file" as
			// the StorageManager and the RSTAR splitting policy.
			PropertySet ps2 = new PropertySet();

			Double f = new Double(0.7);
			ps2.setProperty("FillFactor", f);

			ps2.setProperty("IndexCapacity", capacity);
			ps2.setProperty("LeafCapacity", capacity);
			// Index capacity and leaf capacity may be different.

			int dim = new Integer(2);
			ps2.setProperty("Dimension", dim);

			fRTree = new RTree(ps2, file);
			int id;

			// String line = lr.readLine();
			Set<Integer> fkeys = facilitiesMap.keySet();
			for (int fid : fkeys) {
				Facility facility = facilitiesMap.get(fid);
				// id = f.getId();
				double[] f1 = { facility.getX(), facility.getY() };
				// insert
				Point p = new Point(f1);

				// String data = r.toString();
				// associate some data with this region. I will use a string
				// that represents the
				// region itself, as an example.
				// NOTE: It is not necessary to associate any data here. A
				// null pointer can be used. In that
				// case you should store the data externally. The index will
				// provide the data IDs of
				// the answers to any query, which can be used to access the
				// actual data from the external
				// storage (e.g. a hash table or a database table, etc.).
				// Storing the data in the index is convinient and in case a
				// clustered storage manager is
				// provided (one that stores any node in consecutive pages)
				// performance will improve substantially,
				// since disk accesses will be mostly sequential. On the
				// other hand, the index will need to
				// manipulate the data, resulting in larger overhead. If you
				// use a main memory storage manager,
				// storing the data externally is highly recommended
				// (clustering has no effect).
				// A clustered storage manager is NOT provided yet.
				// Also you will have to take care of converting you data to
				// and from binary format, since only
				// array of bytes can be inserted in the index (see
				// RTree::Node::load and RTree::Node::store for
				// an example of how to do that).

				// tree.insertData(data.getBytes(), r, id);

				fRTree.insertData(null, p, facility.getId()); // main memory
				// example of passing a null pointer as the associated data.
			}

			// // System.err.println("Operations: " + count);
			// System.err.println(tree);
			// System.err.println("Minutes: " + ((end - start) / 1000.0f) /
			// 60.0f);

			// since we created a new RTree, the PropertySet that was used to
			// initialize the structure
			// now contains the IndexIdentifier property, which can be used
			// later to reuse the index.
			// (Remember that multiple indices may reside in the same storage
			// manager at the same time
			// and every one is accessed using its unique IndexIdentifier).
			Integer indexID = (Integer) ps2.getProperty("IndexIdentifier");
			// System.err.println("Index ID: " + indexID);

			boolean ret = fRTree.isIndexValid();
			if (ret == false)
				System.err.println("Structure is INVALID!");

			// flush all pending changes to persistent storage (needed since
			// Java might not call finalize when JVM exits).
			fRTree.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}

		return fRTree;
	}

	/**
	 * 
	 * @param capacity
	 * @param edgesMap
	 * @return an edge rtree
	 */
	static ISpatialIndex RTreeLoadEdges(int capacity,
			Map<Integer, GraphEdge> edgesMap) {
		ISpatialIndex edgeRTree = null;
		try {

			// specify the page size. Since the index may also contain user
			// defined data
			// there is no way to know how big a single node may become. The
			// storage manager
			// will use multiple pages per node if needed. Off course this will
			// slow down performance.

			IStorageManager diskfile = new MemoryStorageManager();
			// IStorageManager diskfile = new DiskStorageManager(ps);

			IBuffer file = new RandomEvictionsBuffer(diskfile, 10, false);
			// applies a main memory random buffer on top of the persistent
			// storage manager
			// (LRU buffer, etc can be created the same way).

			// Create a new, empty, RTree with dimensionality 2, minimum load
			// 70%, using "file" as
			// the StorageManager and the RSTAR splitting policy.
			PropertySet ps2 = new PropertySet();

			Double f = new Double(0.7);
			ps2.setProperty("FillFactor", f);

			ps2.setProperty("IndexCapacity", capacity);
			ps2.setProperty("LeafCapacity", capacity);
			// Index capacity and leaf capacity may be different.

			int dim = new Integer(2);
			ps2.setProperty("Dimension", dim);

			edgeRTree = new RTree(ps2, file);
			int id;

		
			// String line = lr.readLine();
			Set<Integer> edgekeys = edgesMap.keySet();
			for (int eid : edgekeys) {
				GraphEdge e = edgesMap.get(eid);
				id = e.getId();
				double[] f1 = { e.getSrcNode().getX(), e.getSrcNode().getY() };
				double[] f2 = { e.getDestNode().getX(), e.getDestNode().getY() };

				// insert

				Region r = new Region(f1, f2);

				String data = r.toString();
				// associate some data with this region. I will use a string
				// that represents the
				// region itself, as an example.
				// NOTE: It is not necessary to associate any data here. A
				// null pointer can be used. In that
				// case you should store the data externally. The index will
				// provide the data IDs of
				// the answers to any query, which can be used to access the
				// actual data from the external
				// storage (e.g. a hash table or a database table, etc.).
				// Storing the data in the index is convinient and in case a
				// clustered storage manager is
				// provided (one that stores any node in consecutive pages)
				// performance will improve substantially,
				// since disk accesses will be mostly sequential. On the
				// other hand, the index will need to
				// manipulate the data, resulting in larger overhead. If you
				// use a main memory storage manager,
				// storing the data externally is highly recommended
				// (clustering has no effect).
				// A clustered storage manager is NOT provided yet.
				// Also you will have to take care of converting you data to
				// and from binary format, since only
				// array of bytes can be inserted in the index (see
				// RTree::Node::load and RTree::Node::store for
				// an example of how to do that).

				// tree.insertData(data.getBytes(), r, id);

				edgeRTree.insertData(null, r, id); // main memory
				// example of passing a null pointer as the associated data.
			}

			

			// // System.err.println("Operations: " + count);
			// System.err.println(tree);
			// System.err.println("Minutes: " + ((end - start) / 1000.0f) /
			// 60.0f);

			// since we created a new RTree, the PropertySet that was used to
			// initialize the structure
			// now contains the IndexIdentifier property, which can be used
			// later to reuse the index.
			// (Remember that multiple indices may reside in the same storage
			// manager at the same time
			// and every one is accessed using its unique IndexIdentifier).
			Integer indexID = (Integer) ps2.getProperty("IndexIdentifier");
			// System.err.println("Index ID: " + indexID);

			boolean ret = edgeRTree.isIndexValid();
			if (ret == false)
				System.err.println("Structure is INVALID!");

			// flush all pending changes to persistent storage (needed since
			// Java might not call finalize when JVM exits).
			edgeRTree.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}

		return edgeRTree;
	}

}

class FaDist implements Comparable {
	int fid;
	double dist;

	public FaDist(int fid, double dist) {
		this.fid = fid;
		this.dist = dist;
	}

	@Override
	public int compareTo(Object arg0) {
		FaDist fd = (FaDist) arg0;
		if (this.dist > fd.dist)
			return 1;
		else if (this.dist < fd.dist)
			return -1;
		return 0;
	}
}

class SegScore implements Comparable {

	double start;
	double end;
	double score;

	public SegScore(double start, double end, double score) {
		this.start = start;
		this.end = end;
		this.score = score;
	}

	@Override
	public int compareTo(Object arg0) {
		SegScore ss = (SegScore) arg0;
		if (this.start > ss.start)
			return 1;
		else if (this.start < ss.start)
			return -1;
		return 0;
	}

}